1. Field of the Invention
The present invention relates to Viterbi decoders for determining a maximum likelihood path through a trellis created by a convolutional code.
2. Description of the Prior Art
A Viterbi decoder is used to decode convolutional codes, such codes being used to reduce error rates and increase the signal-to-noise ratio in a transmission system over band limited transmission channels. The Viterbi decoder is described in detail in an article entitled "The Viterbi Algorithm" in the Proceedings of the IEEE, Vol. 61, No. 3, March, 1973.
Depending on the encoder design, 2-dimensional convolutional encoding is used as shown in U.S. Pat. No. 4,601,044 to Kromer, III. et al or multidimensional coding (where the number of dimensions is greater than 2) is used as shown in European patent application No. 85300803.5 to Gallager. The Viterbi decoder in the receiver uses the received 2-dimensional or multidimensional signals to estimate the original path of the encoder through the trellis. The maximum likelihood path is determined by finding the possible sequence of 2-dimensional symbol subsets (which trellis path) which is closest to the sequence of received signals. The receiver computes the minimum cost path and from the path history, determines an estimated received symbol.
As to the specific way in which the Viterbi decoder was implemented in the computer programs of the prior art modems, the following description is provided. Referring to FIGS. 1A through 1C, the prior art implementation of the Viterbi decoder will be illustrated in a simple example. In this example, the Viterbi algorithm is used in conjunction with a simple convolutional encoder having four states identified as 0, 1, 2, and 3 in the trellis of FIG. 1A. A convolutional encoder is a finite state device which passes through a succession of the states, with each state being separated in time as shown by time unit j. The trellis is used to diagram all permissible transitions between the present state to the next state of the encoder, with each of the branches between states being identified by a unique encoder binary output, referred to as the subset-selecting bits and designated in FIG. 1A as a, b, c, or d. Each of these subset-selecting bits (a pair of bits in this case) map upon a given subset of symbols.
Beginning at time unit j=m+1, the branch metric is calculated for the paths, i.e., branches, entering each state 0, 1, 2 and 3, as shown in FIG. 1A. For each state at time unit m+1, the survivor path with the smallest metric w' is determined, as shown in FIG. 1B. The paths are stored, either by storing the subset-identifying bits or the states, and the metrics w' for the paths are stored. Referring to FIG. 1C, the unit time j is increased by one. Metrics w" for all of the paths entering the states at j=m+2 are computed by adding calculated branch metrics of the branches from j=m+1 to j=m+2 to the surviving metrics w' of the connecting survivor paths at the preceding unit. At this point, each surviving metric w' includes only the previously calculated branch metric, but with the passing of more time units, each surviving metric w' for a given path will be the summation of all the branch metrics of the path up to that time unit. Again for each state, the path with the smallest metric (the survivor) is selected, eliminating all other paths and reducing the trellis to that shown in FIG. 1C. For each state, the surviving path is stored, together with its metric.
The path histories are extended each time unit as described above. Once the stored path histories are extended so that j=m+L-1 (where L is the truncation length), the decoder finds the minimum cost path (smallest metric) among the surviving paths. For the surviving path, the decoder provides the best estimate of the subset or state at j=m. This is repeated each time unit, so that, e.g., at j=m+L, the decision is made for the state or subset at j+m+1.
There are 2.sup.k states in the trellis (k=2 in this example). Consequently, for each time unit, 2.sup.k words of storage are needed for the survivors and to store the entire path histories, an information sequence of length 2.sup.k .times.L must be stored. As shown in FIG. 2A, the prior art technique for storing these information sequences in memory comprised a memory array as shown. For each time unit, the subset-selecting bits (or states) of a given surviving path are stored in a row. Referring to FIG. 2A, if we assume at time interval j-1 that the subset-selecting bits are ordered in the trillis a, b, c, d and that the extension of the path will result in the subset-selecting bits being reorganized in the order of a, c, b, and d at time unit j, each of the rows representing the path histories must be shifted as shown by the arrows in FIG. 2A to obtain a rearranged memory of FIG. 2B. To accomplish this, it is assumed that the states are sequentially updated. At state 0, register 3 is written in FIG. 2A to the first row in FIG. 2B. As a result, the register 0 is destroyed by register 3. So when state 1 is updated, the survivor in register 0 is lost. One way of solving problem is to store register 3 in a buffer (not shown) and then copy register 2 in FIG. 2A to row 3 in FIG. 2B, register 1 in FIG. 2A to row 2 in FIG. 2B, register 0 in FIG. 2A to row 1 in FIG. 2B, and store the row stored in the buffer back to row 0. For a convolutional code with many states, the algorithm is very complex.
Consequently, from an implementation point of view, each time j is updated, each state could come from multiple states of time j-1. Therefore, all the paths need to be reshuffled according to the new order of the subset-selecting bits at time j. In addition, in order to rearrange the path of a particular state when the survivors of all the other states have not been determined, it is necessary to have temporary buffers to prevent overwriting of the path's history. An alternative would be to maintain two tables.
As a result of this prior art design, at each time instant j, the operation of reading the past paths and writing to the new locations is required. For a convolutional code with many states, it creates a great number of data moves. For example, a 64 states convolutional code with a truncation length of 20 needs 64.times.20 read and write operations.
In prior art schemes the states have been stored instead of the subset-selecting bits and a look-up table has been used to generate the subset-selecting bits, when needed. In other words, in the above example, with the knowledge of two sequential inputs to the encoder, i.e., the old and new states, an output of the encoder, i.e., the subset-selecting bits, can be determined or vice versa. Since the encoder adds one bit of redundancy per time unit, the prior art scheme took advantage of this fact by storing the input of the encoder instead of the required output, so as to reduce memory requirements at the cost of having to use the lookup table to recreate the subset-selecting bits.
The above example is for 2-dimensional coded modulation wherein the output of the encoder consists of subset-defining bits that map onto two-dimensional subsets of signal points. The unit time is one baud, i.e., symbol interval or modulation period. The above example is also applicable to an N-dimensional coded modulation system (N&gt;2), wherein the subset-defining bits map onto a multidimensional subset. In this case, the unit time is a group interval comprising a plurality of bauds and the trellis has parallel branches between states.